package 剑指offer;

import common.ListNode;

import java.util.HashSet;
import java.util.Set;

/**
 * @author zhangmin
 * @create 2021-11-22 9:28
 *
 * 双指针
 */
public class day12_25_52 {
    /**===========================================================================================================================
     * 剑指 Offer 25. 合并两个排序的链表
     * 输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
     * */
    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        if (l1==null) return l2;
        if (l2==null) return l1;
        ListNode p1=l1,p2=l2;
        ListNode head;
        if (p1.val<p2.val){
            head=p1;
            p1=p1.next;
        }else {
            head=p2;
            p2=p2.next;
        }
        ListNode resHead=head;
        while (p1!=null&&p2!=null){
            if (p1.val<p2.val){
                head.next=p1;
                p1=p1.next;
            }else {
                head.next=p2;
                p2=p2.next;
            }
            head=head.next;
        }
        if (p1!=null){
            head.next=p1;
        }else {
            head.next=p2;
        }
        return resHead;
    }
    //代码简化：加入虚假的头节点
    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        ListNode resHead=new ListNode(0);
        ListNode cur=resHead;
        while (l1!=null&&l2!=null){
            if (l1.val<l2.val){
                cur.next=l1;
                l1=l1.next;
            }else {
                cur.next=l2;
                l2=l2.next;
            }
            cur=cur.next;
        }
        cur.next=l1!=null? l1:l2;
        return resHead.next;
    }
    //递归
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1==null) return l2;
        if (l2==null) return l1;
        if (l1.val<l2.val){
            l1.next=mergeTwoLists(l1.next,l2);
            return l1;
        }else {
            l2.next=mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
    /**===========================================================================================================================
     * 剑指 Offer 52. 两个链表的第一个公共节点
     * 输入两个链表，找出它们的第一个公共节点
     * 1、用哈希表存储，然后判断
     * 2、双指针：两个指针在遍历完当前链表后，换到另一个链表的头部，直到两者相遇。在指针 pA 移动了 a+c+b次、指针 pB 移动了 b+c+a次之后，两个指针会同时到达两个链表的第一个公共节点
     * */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        Set<ListNode> set=new HashSet<>();
        if (headA==null||headB==null) return null;
        while (headA!=null){
            set.add(headA);
            headA=headA.next;
        }
        while (headB!=null){
            if (set.contains(headB))
                return headB;
            headB=headB.next;
        }
        return null;
    }
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA==null||headB==null) return null;
        ListNode pa=headA,pb=headB;
        while (pa!=pb){
            if (pa==null){
                pa=headB;
            }else {
                pa=pa.next;
            }
            if (pb==null){
                pb=headA;
            }else {
                pb=pb.next;
            }
        }
        return pa;
    }
}
